/*
 * (C) Copyright 2014-2016, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.tree

import org.jheaps.AddressableHeap
import org.jheaps.MergeableAddressableHeap
import org.jheaps.annotations.ConstantTime
import org.jheaps.annotations.LogarithmicTime
import java.io.Serializable

/**
 * Skew heaps. The heap is sorted according to the [ natural ordering][Comparable] of its keys, or by a [Comparator] provided at heap
 * creation time, depending on which constructor is used.
 *
 *
 *
 * Operations `insert`, `deleteMin`, and `delete` take
 * amortized O(log(n)). Operation `findMin` is worst-case O(1). Note that
 * a skew-heap does not efficiently support the operation `decreaseKey`
 * which is amortized &#937;(log(n)).
 *
 *
 *
 * Note that the ordering maintained by this heap, like any heap, and whether or
 * not an explicit comparator is provided, must be *consistent with
 * `equals`* if this heap is to correctly implement the `Heap`
 * interface. (See `Comparable` or `Comparator` for a precise
 * definition of *consistent with equals*.) This is so because the
 * `Heap` interface is defined in terms of the `equals` operation,
 * but this heap performs all key comparisons using its `compareTo` (or
 * `compare`) method, so two keys that are deemed equal by this method
 * are, from the standpoint of this heap, equal. The behavior of a heap
 * *is* well-defined even if its ordering is inconsistent with
 * `equals`; it just fails to obey the general contract of the
 * `Heap` interface.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <K>
 * the type of keys maintained by this heap
 * @param <V>
 * the type of values maintained by this heap
 *
 * @author Dimitrios Michail
</V></K> */
open class SkewHeap<K, V> @JvmOverloads constructor(
    /**
     * The comparator used to maintain order in this heap, or null if it uses
     * the natural ordering of its keys.
     *
     * @serial
     */
    protected val comparator: Comparator<in K?>? = null
) : MergeableAddressableHeap<K, V>, Serializable {

    /**
     * Size of the heap
     */
    protected var size: Long

    /**
     * Root node of the heap
     */
    protected var root: Node?

    /**
     * Used to reference the current heap or some other heap in case of melding,
     * so that handles remain valid even after a meld, without having to iterate
     * over them.
     *
     * In order to avoid maintaining a full-fledged union-find data structure,
     * we disallow a heap to be used in melding more than once. We use however,
     * path-compression in case of cascading melds, that it, a handle moves from
     * one heap to another and then another.
     */
    protected var other: SkewHeap<K, V>

    /**
     * Constructs a new, empty heap, ordered according to the given comparator.
     *
     *
     *
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     */
    /**
     * Constructs a new, empty heap, using the natural ordering of its keys.
     *
     *
     *
     * All keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     */
    init {
        this.size = 0
        this.root = null
        this.other = this
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime(amortized = true)
    override fun insert(key: K):Node {
        return insert(key, null)
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime(amortized = true)
    override fun insert(key: K, value: V?): Node {
        check(other === this) { "A heap cannot be used after a meld" }
        if (key == null) {
            throw NullPointerException("Null keys not permitted")
        }
        val n = createNode(key, value)

        // easy special cases
        if (size == 0L) {
            root = n
            size = 1
            return n
        } else if (size == 1L) {
            val c = comparator?.compare(key, root!!.key) ?: (key as Comparable<K?>).compareTo(root!!.key)
            if (c <= 0) {
                n.o_c = root
                root!!.y_s = n
                root = n
            } else {
                root!!.o_c = n
                n.y_s = root
            }
            size = 2
            return n
        }

        root = if (comparator == null) {
            union(root, n)
        } else {
            unionWithComparator(root, n)
        }
        size++

        return n
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun findMin(): Node {
        if (size == 0L) {
            throw NoSuchElementException()
        }
        return root!!
    }

    /**
     * {@inheritDoc}
     */
    @LogarithmicTime(amortized = true)
    override fun deleteMin(): Node {
        if (size == 0L) {
            throw NoSuchElementException()
        }
        val oldRoot = root!!

        // easy special cases
        if (size == 1L) {
            root = null
            size = 0
            return oldRoot
        } else if (size == 2L) {
            root = root!!.o_c
            root!!.o_c = null
            root!!.y_s = null
            size = 1
            oldRoot.o_c = null
            return oldRoot
        }

        root = unlinkAndUnionChildren(root!!)
        size--

        return oldRoot
    }

    @get:ConstantTime
    override val isEmpty: Boolean
        /**
         * {@inheritDoc}
         */
        get() = size == 0L

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun size(): Long {
        return size
    }

    /**
     * {@inheritDoc}
     */
    override fun comparator(): Comparator<in K?>? {
        return comparator
    }

    /**
     * {@inheritDoc}
     */
    @ConstantTime
    override fun clear() {
        root = null
        size = 0
    }

    override fun meld(other: MergeableAddressableHeap<K, V>) {
        val h = other as SkewHeap<K, V>

        // check same comparator
        if (comparator != null) {
            require(!(h.comparator == null || h.comparator != comparator)) { "Cannot meld heaps using different comparators!" }
        } else require(h.comparator == null) { "Cannot meld heaps using different comparators!" }

        check(h.other === h) { "A heap cannot be used after a meld." }

        // perform the meld
        size += h.size
        root = if (comparator == null) {
            union(root, h.root)
        } else {
            unionWithComparator(root, h.root)
        }

        // clear other
        h.size = 0
        h.root = null

        // take ownership
        h.other = this
    }

    // ~-----------------------------------------------------------------------------
    /*
     * We maintain explicitly the belonging heap, instead of using an inner
     * class due to possible cascading melding.
     */
    open inner class Node(
         var heap: SkewHeap<K, V>, override var key: K, override var value: V?
    ) : AddressableHeap.Handle<K, V>, Serializable {
        var o_c: Node? = null // older child
        var y_s: Node? = null // younger sibling or parent

        override fun decreaseKey(newKey: K) {
            owner.decreaseKey(this, newKey)
        }

        override fun delete() {
            owner.delete(this)
        }

        /*
         * Get the owner heap of the handle. This is union-find with
         * path-compression between heaps.
         */
        val owner: SkewHeap<K, V>
            get() {
                if (heap.other !== heap) {
                    // find root
                    var root = heap
                    while (root !== root.other) {
                        root = root.other
                    }
                    // path-compression
                    var cur = heap
                    while (cur.other !== root) {
                        val next = cur.other
                        cur.other = root
                        cur = next
                    }
                    heap = root
                }
                return heap
            }

    }

    private fun decreaseKey(n: Node, newKey: K) {
        val c = comparator?.compare(newKey, n.key) ?: (newKey as Comparable<K?>).compareTo(n.key)

        require(c <= 0) { "Keys can only be decreased!" }
        if (c == 0 || root === n) {
            n.key = newKey
            return
        }

        /*
         * Delete and reinsert
         */
        delete(n)
        n.key = newKey
        root = if (comparator == null) {
            union(root, n)
        } else {
            unionWithComparator(root, n)
        }
        size++
    }

    /**
     * Create a new node.
     *
     * @param key
     * the key
     * @param value
     * the value
     * @return the newly created node
     */
    protected open fun createNode(key: K, value: V?): Node {
        return Node(this, key, value)
    }

    /**
     * Delete a node from the heap.
     *
     * @param n
     * the node
     */
    protected fun delete(n: Node) {
        if (n === root) {
            deleteMin()
            return
        }

        requireNotNull(n.y_s) { "Invalid handle!" }

        // disconnect and union children of node
        val childTree = unlinkAndUnionChildren(n)

        // find parent
        val p = getParent(n)

        // link children tree in place of node
        if (childTree == null) {
            // no children, just unlink from parent
            if (p!!.o_c === n) {
                if (n.y_s === p) {
                    p!!.o_c = null
                } else {
                    p!!.o_c = n.y_s
                }
            } else {
                p!!.o_c!!.y_s = p
            }
        } else {
            // link children tree to parent
            if (p!!.o_c === n) {
                childTree.y_s = n.y_s
                p!!.o_c = childTree
            } else {
                p!!.o_c!!.y_s = childTree
                childTree.y_s = p
            }
        }

        size--
        n.o_c = null
        n.y_s = null
    }

    /**
     * Unlink the two children of a node and union them forming a new tree.
     *
     * @param n
     * the node
     * @return the tree which is formed by the two children subtrees of the node
     */
    protected fun unlinkAndUnionChildren(n: Node): Node? {
        // disconnect children
        val child1 = n.o_c ?: return null
        n.o_c = null

        var child2 = child1.y_s
        if (child2 === n) {
            child2 = null
        } else {
            child2!!.y_s = null
        }
        child1.y_s = null

        return if (comparator == null) {
            union(child1, child2)
        } else {
            unionWithComparator(child1, child2)
        }
    }

    /**
     * Get the parent node of a given node.
     *
     * @param n
     * the node
     * @return the parent of a node
     */
    protected fun getParent(n: Node): Node? {
        if (n.y_s == null) {
            return null
        }
        val c = n.y_s
        if (c!!.o_c === n) {
            return c
        }
        val p1 = c!!.y_s
        if (p1 != null && p1.o_c === n) {
            return p1
        }
        return c
    }

    /**
     * Unlink the right child of a node.
     *
     * @param n
     * the node
     * @return the right child after unlinking
     */
    protected fun <U:Node> unlinkRightChild(n: U): U? {
        val left = n.o_c
        if (left == null || left.y_s === n) {
            return null
        }
        val right = left.y_s
        left.y_s = n
        right!!.y_s = null
        return right as U
    }

    /**
     * Top-down union of two skew heaps.
     *
     * @param root1
     * the root of the first heap
     * @param root2
     * the root of the right heap
     * @return the new root of the merged heap
     */
    protected open fun union(root1: Node?, root2: Node?): Node? {
        var root1 = root1
        var root2 = root2
        if (root1 == null) {
            return root2
        } else if (root2 == null) {
            return root1
        }

        val newRoot: Node
        var cur: Node

        // find initial
        var c = (root1.key as Comparable<K?>?)!!.compareTo(root2.key)
        if (c <= 0) {
            newRoot = root1
            root1 = unlinkRightChild(root1)
        } else {
            newRoot = root2
            root2 = unlinkRightChild(root2)
        }
        cur = newRoot

        // merge
        while (root1 != null && root2 != null) {
            c = (root1.key as Comparable<K?>?)!!.compareTo(root2.key)
            if (c <= 0) {
                // link as left child of cur
                if (cur.o_c == null) {
                    root1.y_s = cur
                } else {
                    root1.y_s = cur.o_c
                }
                cur.o_c = root1
                cur = root1
                root1 = unlinkRightChild(root1)
            } else {
                // link as left child of cur
                if (cur.o_c == null) {
                    root2.y_s = cur
                } else {
                    root2.y_s = cur.o_c
                }
                cur.o_c = root2
                cur = root2
                root2 = unlinkRightChild(root2)
            }
        }

        while (root1 != null) {
            // link as left child of cur
            if (cur.o_c == null) {
                root1.y_s = cur
            } else {
                root1.y_s = cur.o_c
            }
            cur.o_c = root1
            cur = root1
            root1 = unlinkRightChild(root1)
        }

        while (root2 != null) {
            // link as left child of cur
            if (cur.o_c == null) {
                root2.y_s = cur
            } else {
                root2.y_s = cur.o_c
            }
            cur.o_c = root2
            cur = root2
            root2 = unlinkRightChild(root2)
        }

        return newRoot
    }

    /**
     * Top-down union of two skew heaps with comparator.
     *
     * @param root1
     * the root of the first heap
     * @param root2
     * the root of the right heap
     * @return the new root of the merged heap
     */
    protected open fun unionWithComparator(root1: Node?, root2: Node?): Node? {
        var root1 = root1
        var root2 = root2
        if (root1 == null) {
            return root2
        } else if (root2 == null) {
            return root1
        }

        val newRoot: Node
        var cur: Node

        // find initial
        var c = comparator!!.compare(root1.key, root2.key)
        if (c <= 0) {
            newRoot = root1
            root1 = unlinkRightChild(root1)
        } else {
            newRoot = root2
            root2 = unlinkRightChild(root2)
        }
        cur = newRoot

        // merge
        while (root1 != null && root2 != null) {
            c = comparator.compare(root1.key, root2.key)
            if (c <= 0) {
                // link as left child of cur
                if (cur.o_c == null) {
                    root1.y_s = cur
                } else {
                    root1.y_s = cur.o_c
                }
                cur.o_c = root1
                cur = root1
                root1 = unlinkRightChild(root1)
            } else {
                // link as left child of cur
                if (cur.o_c == null) {
                    root2.y_s = cur
                } else {
                    root2.y_s = cur.o_c
                }
                cur.o_c = root2
                cur = root2
                root2 = unlinkRightChild(root2)
            }
        }

        while (root1 != null) {
            // link as left child of cur
            if (cur.o_c == null) {
                root1.y_s = cur
            } else {
                root1.y_s = cur.o_c
            }
            cur.o_c = root1
            cur = root1
            root1 = unlinkRightChild(root1)
        }

        while (root2 != null) {
            // link as left child of cur
            if (cur.o_c == null) {
                root2.y_s = cur
            } else {
                root2.y_s = cur.o_c
            }
            cur.o_c = root2
            cur = root2
            root2 = unlinkRightChild(root2)
        }

        return newRoot
    }

    companion object {
        private const val serialVersionUID: Long = 1
    }
}
